package com.sxt;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**基于树形结构实现元素存储的容器*/
public class MyTree01<E> {
    //创建两Map  一个用于方便查子结点  一个方便用于查父结点
  private Map<E,E> map = new HashMap<>();
   private Map<E,List<E>> map2 = new HashMap<>();

    //添加元素
    public void add(E parent,E item){
        //先完成单节点之间的映射 方便获取父结点 (由下往上)
        this.map.put(item,parent);
        //完成多节点之间的映射  方便获取子结点（由上往下）
        List<E> list = this.map2.get(parent);
        if(list == null){
            list = new ArrayList<>();
            this.map2.put(parent,list);
        }
        list.add(item);
    }

    //获取当前结点的父结点
    public E getParent(E item){

        return this.map.get(item);
    }
    //获取当前结点的子结点  可能有多个子结点，所以用List容器存储
    public List<E> getChild(E item){

        return this.map2.get(item);
    }

    //获取当前结点的兄弟结点
    public List<E> getBrother(E item){
        //获取父结点
        E parent = this.map.get(item);
        //获取子结点
        List<E> list = this.getChild(parent);
        //创建新结点
        List<E> brother = new ArrayList<>();
        if(list != null){
            brother.addAll(list);
            brother.remove(item);
        }
        return brother;
    }
    //获取当前结点的的祖先结点
    public List<E> getForefather(E item){
        //获取当前结点的父结点
        E parent = this.getParent(item);
        if(parent == null){
            return new ArrayList<>();
        }
        //递归调用，再次获取当前结点的父结点
        List<E> list = this.getForefather(parent);
        list.add(parent);
        return list;
    }
    //获取当前结点的子孙结点
    public List<E> getGrandChildren(E item){
        //存放所有子孙结点中的元素
        List<E> list = new ArrayList<>();
        //获取当前结点的子结点
        List<E> child = this.getChild(item);
        //结束递归条件
        if(child == null){
            return list;
        }
        for(int i=0;i< child.size();i++){
            /*获取元素*/
            E temp = child.get(i);
            //利用递归，获取当前结点的子结点
            List<E> value = this.getGrandChildren(temp);
            list.add(temp);
            list.addAll(value);
        }

        return list;
    }

    public static void main(String[] args) {
        //实例化容器
        MyTree01<String> myTree01 = new MyTree01<>();
        myTree01.add("root","生物");
        myTree01.add("生物","植物");
        myTree01.add("生物","动物");
        myTree01.add("生物","菌类");
        myTree01.add("动物","脊椎动物");
        myTree01.add("动物","脊索动物");
        myTree01.add("动物","腔肠动物物");
        myTree01.add("脊椎动物","哺乳动物");
        myTree01.add("脊椎动物","鱼");
        myTree01.add("哺乳动物","猫");
        myTree01.add("哺乳动物","牛");
        myTree01.add("哺乳动物","人");
        System.out.println("-----获取父节点------");
        String parent = myTree01.getParent("鱼");
        System.out.println(parent);
        System.out.println("-------获取子结点----");
        List<String> child = myTree01.getChild("动物");
        for(int i=0;i< child.size();i++){
            System.out.println(child.get(i));
        }
        System.out.println("-------获取兄弟结点----");
        List<String> brother = myTree01.getBrother("脊椎动物");
        for(int i=0;i<brother.size();i++){
            System.out.println(brother.get(i));
        }
        System.out.println("-------获取祖先结点----");
        List<String> forFather = myTree01.getForefather("人");
        for(int i=0;i<forFather.size();i++){
            System.out.println(forFather.get(i));
        }
        System.out.println("-------获取子孙结点----");
        List<String> grandChildren = myTree01.getGrandChildren("root");
        for(int i=0;i<grandChildren.size();i++){
            System.out.println(grandChildren.get(i));
        }
    }
}
